class ListNode {
    val: number
    next: ListNode | null
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.next = (next === undefined ? null : next)
    }
}


/**
 * https://leetcode-cn.com/problems/partition-list/
 * 分隔链表 (保留元素的相对位置)
 * @param head 
 * @param x 
 */
const partition = (head: ListNode | null, x: number): ListNode | null => {

    // 边界判断
    if (head === null || head.next === null) return head;

    // 新建虚拟头节点
    const dummyHead = new ListNode(0);
    dummyHead.next = head;

    // 大于等于x的位置
    let sorted = dummyHead.next,
        large = dummyHead.next,
        // 找到了比x大的数了
        po = false,
        // 移动的
        curr: ListNode | null = dummyHead.next;

    // 一直往下遍历
    let prev = dummyHead;

    while (curr !== null) {
        // 保存next
        const n: ListNode | null = curr.next
        if (!po) {
            // 还没有找到比po大的数
            if (curr.val >= x) {
                // 找到了比x大的数
                po = true;

                // 保存比x的大数的前一个节点
                sorted = prev;

                // 保存比x的节点
                large = curr;
            }
            prev = curr
        } else {
            if (curr.val < Math.min(large.val, x)) {
                // 当前节点小于了大于等于x节点的值, 需要移动

                // 移除该节点
                prev.next = curr.next;

                // 更改指向
                curr.next = sorted.next;
                sorted.next = curr;

                // 更改sorted
                sorted = curr;

                // prev不用变
            } else {
                prev = curr
            }
        }

        // 继续往下
        curr = n;
    }

    return dummyHead.next
};

/**
 * https://leetcode-cn.com/problems/partition-list/
 * 分隔链表 (不要保留元素的相对位置)
 * @param head 
 * @param x 
 */
const partition2 = (head: ListNode | null, x: number): ListNode | null => {

    // 边界判断
    if (head === null || head.next === null) return head;

    // left存放比x小的, right反之 
    let left = new ListNode(0),
        right = new ListNode(0),
        l = left,
        r = right;

    while (head !== null) {
        if (head.val < x) {
            // 比x小, 放左边
            l = l.next = head;
        } else {
            // 比x大, 放右边
            r = r.next = head;
        }
        // 下一个处理
        head = head.next;
    }
    // 指向右边的头, 连接起来 
    l.next = right.next;

    // 必须添加, 防止链表形成循环 
    r.next = null
    return left.next;
};

/**
 * https://leetcode-cn.com/problems/partition-list/
 * 分隔链表 (不要保留元素的相对位置)
 * @param head 
 * @param x 
 */
const partition3 = (head: ListNode | null, x: number): ListNode | null => {

    // 边界判断
    if (head === null || head.next === null) return head;

    // 新建虚拟头节点
    const dummyHead = new ListNode(0);
    dummyHead.next = head;

    let curr: ListNode | null = dummyHead.next,
        po = false,
        prev = dummyHead;

    // debugger
    while (curr !== null) {
        const n: ListNode | null = curr.next;
        if (!po) {
            if (curr.val >= x) {
                // 后面要移动了 
                po = true;
            }

        } else {
            // 只要发现比较x小的, 往第一个节点插入
            if (curr.val < x) {
                // 指向该节点的去掉
                if (prev !== dummyHead) {
                    prev.next = curr.next
                    curr.next = dummyHead.next;
                    dummyHead.next = curr;

                    // 不用更改prev
                    curr = n;
                    continue
                }
            }
        }

        // 保存前一个节点
        prev = curr;
        // 继续往下
        curr = n;
    }

    return dummyHead.next
};



export { }

const headA = new ListNode(1);
headA.next = new ListNode(2)
headA.next.next = new ListNode(3)
// headA.next.next.next = new ListNode(2)
// headA.next.next.next.next = new ListNode(5)
// headA.next.next.next.next.next = new ListNode(2)
console.log(partition2(headA, 4))